package es.deusto.ingenieria.is.search.tsp.algorithms.blind;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import es.deusto.ingenieria.is.search.algorithms.Node;
import es.deusto.ingenieria.is.search.algorithms.heuristic.EvaluationFunction;
import es.deusto.ingenieria.is.search.algorithms.heuristic.HeuristicSearchMethod;
import es.deusto.ingenieria.is.search.formulation.Operator;
import es.deusto.ingenieria.is.search.formulation.Problem;
import es.deusto.ingenieria.is.search.formulation.State;

/** Clase que realiza la funcionalidad de Coste Uniforma, para ello hereda de los metodos heuristicos de busqueda.
 * @author Inigo y Kevin
 *
 */
public class UniformedCostSearch extends HeuristicSearchMethod{

	/** Constructor por defecto de la clase, recibe como parametor la funcion de evaluacion y se la manda al constructor padre.
	 * @param EvaluationFunction
	 */
	public UniformedCostSearch(EvaluationFunction arg0) {
		super(arg0);
	}
	
	/* (non-Javadoc) Metodo de busqueda de Coste Uniforme
	 * @see es.deusto.ingenieria.is.search.algorithms.SearchMethod#search(es.deusto.ingenieria.is.search.formulation.Problem, es.deusto.ingenieria.is.search.formulation.State)
	 */
	@Override
	public Node search(Problem arg0, State arg1) {
				//Lista frontier que almacena los nodos durante el proceso.
				List<Node> frontier = new ArrayList<Node>();
				//Lista de nodos generados durante el proceso de busqueda, util para para comprobar los estados repetidos.
				List<State> generatedStates = new ArrayList<State>();
				
				//Lista de estados expandido durante el proceso, util para para comprobar los estados repetidos
				List<State> expandedStates = new ArrayList<State>();
				//Primer nodo de la lista
				Node firstNode = null;
				//Nodos sucesores
				List<Node> successorNodes = null;
				//Variable booleana que almacena si la solucion ha sido encontrada
				boolean solutionFound = false;	

				
				frontier.add(new Node(arg1));

				//Bucle en el que se busca la solucion del problema
				while (!solutionFound && !frontier.isEmpty()) {			
					//Se borra el primer nodo de la lista frontier y lo almacenamos en una variable
					firstNode = frontier.remove(0);			
					//SI el nodo almacenado es estado final ha finalizado el problema. EN caso contrario se procede a realizar una expansion
					if (arg0.isFinalState(firstNode.getState())) {
						
						solutionFound = true;
								
					} else {
						
						successorNodes = this.expand(firstNode, arg0, generatedStates, expandedStates);
						
						if (successorNodes != null && !successorNodes.isEmpty()) {
							
							frontier.addAll(successorNodes);
							
							Collections.sort(frontier);
						}
					}
				}
				
				// Si se ha encontrado la solucion se devuelve el primer nodo y sino devuelve null
				if (solutionFound) {
					
					return firstNode;
				
				} else {
					
					return null;
				}
	}
	
	/* (non-Javadoc) Metodo que realiza la funcion de expansion del coste uniforme
	 * @see es.deusto.ingenieria.is.search.algorithms.SearchMethod#expand(es.deusto.ingenieria.is.search.algorithms.Node, es.deusto.ingenieria.is.search.formulation.Problem, java.util.List, java.util.List)
	 */
	protected List<Node> expand(Node node, Problem problem, List<State> generatedStates, List<State> expandedStates) {
		List<Node> successorNodes = new ArrayList<Node>();
		Node successorNode = null;
		State currentState = null;
		State successorState = null;
		
		//SI el nodo actual y el problema no son nulos se realiza el proceso de expansion
		if (node != null && problem != null) {
			
			currentState = node.getState();
			
			generatedStates.remove(currentState);
			expandedStates.add(currentState);			
			
			if (currentState != null) {
				
				for (Operator operator : problem.getOperators()) {
					
					successorState = operator.apply(currentState);
					
					if (successorState != null) {
						
						if (!generatedStates.contains(successorState) && !expandedStates.contains(successorState)) {
							
							successorNode = new Node(successorState);
							successorNode.setOperator(operator.getName());
							successorNode.setParent(node);
							successorNode.setDepth(node.getDepth() + 1);
							successorNode.setG(this.getEvaluationFunction().calculateG(successorNode));
							successorNodes.add(successorNode);
							
							generatedStates.add(successorState);
						}
					}
				}
			}
		}
		
		return successorNodes;
	}
	
	

}
